function tokenizer(input) {
    let index = 0
    const tokens = []
    while (index < input.length) {
        let char = input[index]
        // 处理空格
        if (char === ' ') {
            index++
            continue
        }
        // 处理左括号
        if (char === '(') {
            tokens.push({ type: 'paren', value: '(' })
            index++
            continue
        }
        // 提取函数名称：全部为英文字母，支持大小写
        const fuctionReg = /[a-z]/i
        if (fuctionReg.test(char)) {
            let functionName = ''
            while (fuctionReg.test(char)) {
                functionName += char
                char = input[++index]
            }
            tokens.push({ type: 'name', value: functionName })
            continue
        }
        // 提取数字，只支持非负整数
        const numberReg = /[0-9]/
        if (numberReg.test(char)) {
            let number = ''
            while (numberReg.test(char)) {
                number += char
                char = input[++index]
            }
            tokens.push({ type: 'number', value: number })
            continue
        }
        // 处理右括号
        if (char === ')') {
            tokens.push({ type: 'paren', value: ')' })
            index++
            continue
        }
        throw new TypeError('未知类型字符')
    }
    return tokens
}

function parser(tokens) {
    function walk(tokens) {
        const nodes = []
        while (tokens.length > 0) {
            const token = tokens.shift()
            if (token.type === 'name') {
                nodes.push({ type: 'CallExpression', name: token.value, params: walk(tokens) })
                continue
            }
            if (token.type === 'number') {
                nodes.push({ type: 'NumberLiteral', value: token.value })
                continue
            }
            if (token.type === 'paren' && token.value === '(') {
                continue
            }
            if (token.type === 'paren' && token.value === ')') {
                break
            }
            throw new TypeError('类型不正确，不支持' + token.type)
        }
        return nodes
    }
    return { type: 'Program', body: walk(tokens) }
}

function traverser(ast, visitor) {
    const arrayTraverser = (arr, parent) => {
        arr.forEach(item => { nodeTraverser(parent, item) })
    }
    const nodeTraverser = (parent, node) => {
        const { type } = node
        const method = visitor[type]
        if (method) {
            method(parent, node)
        }
        if (type === 'Program') {
            arrayTraverser(node.body, node)
        } else if (type === 'CallExpression') {
            arrayTraverser(node.params, node)
        } else if (type !== 'NumberLiteral') {
            throw new TypeError('不支持当前类型' + type)
        }
    }
    return nodeTraverser(null, ast)
}
function transformer(ast) {
    ast._context = []
    traverser(ast, {
        NumberLiteral(parent, node) {
            parent._context.push({ type: 'NumberLiteral', value: node.value })
        },
        CallExpression(parent, node) {
            let expression = {
                type: 'CallExpression',
                callee: { type: 'Identifier', name: node.name },
                arguments: []
            }
            node._context = expression.arguments
            if (parent.type === 'Program') {
                expression = { type: 'ExpressionStatement', expression }
            }
            parent._context.push(expression)
        }
    })
    return { type: 'Program', body: ast._context }
}
function codeGenerator(newAst) {
    switch (newAst.type) {
        case 'Program':
            // 处理根节点
            return newAst.body.map(codeGenerator).join('\m')
        case 'ExpressionStatement':
            // 编译代码行
            return codeGenerator(newAst.expression) + ';'
        case 'CallExpression':
            // 处理函数
            return newAst.callee.name + '(' + newAst.arguments.map(codeGenerator).join(',') + ')'
        case 'NumberLiteral':
            return newAst.value
        default:
            throw new TypeError('类型有误' + node.type)
    }
}
const tokens = tokenizer('(add 2 (subtract 4 2))')
const ast = parser(tokens)
const newAst = transformer(ast)
const code = codeGenerator(newAst)
console.log(code)

